
template<typename T>
class MergeSortClass
{
private:
	T *arr;
	T *holdArr;
	size_t length;
public:
	MergeSortClass(T* arr, size_t len):arr(arr),length(len),holdArr(NULL){holdArr=new T[length];}
	~MergeSortClass(){
		if(holdArr)
		{
			if(length>1)
				delete []holdArr;
			else if(length==1)
				delete holdArr;
		}
	}
	inline void MergeSort();
	inline void MergeSort(size_t startPos, size_t endPos);
	inline void Merge(size_t startPos,size_t endPos1, size_t endPos2);
};
template<typename T>
void MergeSortClass<T>::MergeSort(size_t startPos,size_t endPos)
{
	if(startPos<endPos)
	{
		size_t middle = (startPos+endPos)/2;
		MergeSort(startPos,middle);
		MergeSort(middle+1,endPos);
		Merge(startPos,middle,endPos);
	}
}
template<typename T>
void MergeSortClass<T>:: MergeSort()
{
	if(length>1)
		MergeSort(0,length-1);
	else if(length==1)
		return;
	else
	{
		printf("Error: Array size must be positive!\n");
		exit(1);
	}
}
template<typename T>
void MergeSortClass<T>::Merge(size_t startPos,size_t endPos1, size_t endPos2)
{
	for(size_t i=startPos;i<=endPos2;++i)
		holdArr[i]=arr[i];
	size_t startPos1=startPos;
	size_t startPos2=endPos1+1;
	size_t totalPos=startPos;
	while(startPos1<=endPos1 || startPos2<=endPos2)
	{
		if(startPos1>endPos1)
		{
			arr[totalPos++]=holdArr[startPos2++];
		}
		else if(startPos2>endPos2)
		{
			arr[totalPos++]=holdArr[startPos1++];
		}
		else if(holdArr[startPos1]>holdArr[startPos2])
			arr[totalPos++]=holdArr[startPos2++];
		else
			arr[totalPos++]=holdArr[startPos1++];
	}
	if(totalPos!=endPos2+1)
	{
		printf("Error: size not match!\n");
		exit(1);
	}
}

template<typename T>
void MergeSort(T* vec,size_t cnt)
{
	MergeSortClass<T> mergeSort(vec,cnt);
	mergeSort.MergeSort();
}